The Voronoi diagram and its related concepts have been quite popular in various technical fields such as science and engineering fields. In particular, the use of Voronoi diagram for a point set has been increasing over the last few years with respect to various applications. This can be attributed to a greater understanding of its mathematical and computational properties, as well as the development of dynamic and efficient codes.
In biology, for example, the Voronoi diagram for the centers of atoms in a molecule was first used by Richards in 1974 to study the packing density of molecules (see F. M. Richards, The interpretation of protein structures: Total volume, group volume distributions and packing density, Journal of Molecular Biology 82 (1974) 1-14). Since then the Voronoi diagram has been used as one of the most important computational tools for conducting structure analysis of molecules.
Since 1974, the Voronoi diagram of a point set has been used quite extensively in the solution processes of various structural biological problems. However, Richards realized that the ordinary Voronoi diagram of points cannot adequately account for the size variations among atoms. As such, Richards proposed to translate the planar bisector between two atoms in the Voronoi diagram according to the size differences between two atoms. However, the translations of bisectors caused the so-called “vertex error” since this transformation cannot generally guarantee a correct tessellation of the space. In 1982, Gellatly and Finney proposed using a radical plane as the bisector between two atoms since such planes can guarantee that vertex errors will not occur (see B. J. Gellatly, J. L. Finney, Calculation of protein volumes: An alternative to the Voronoi procedure, Journal of Molecular Biology 161 (2) (1982) 305-322). While reflecting the size variations among atoms at a certain level, this transformation can guarantee a valid tessellation of the space. The tessellation using radical planes is indeed identical to the power diagram named by Aurenhammer (see F. Aurenhammer, Power diagrams: Properties, algorithms and applications, SIAM Journal on Computing 16 (1987) 78-96).
By introducing the concept of alpha-shapes in 1994, Edelsbrunner and Muecke provided a basis for applying the Voronoi diagram of a point set in reconstructing the shape from which the point set can be produced (see H. Edelsbrunner, E. P. Muecke, Three-dimensional alpha shapes, ACM Transactions on Graphics 13 (1) (1994) 43-72). They also provided an efficient code to compute alpha-shapes using the properties of Delaunay triangulation. Since alpha-shapes are fundamentally based on the rigorous theory of the Voronoi diagram for a point set and the Delaunay triangulation, they have been used in various applications. The main applications of alpha-shapes lie in deriving the surface shape, which is defined by a point set. Based on this property, many researchers have tried to use alpha-shapes for restructuring and deriving the spatial structures of biological systems.
However, alpha-shapes have limitations in their applications in biological systems mainly due to the fact that alpha-shapes can not account for the size variations among atoms. In general, the proximity among spheres is not necessarily identical to the proximity among centers of spheres.
The three-dimensional alpha-shape will be briefly reviewed with reference to FIGS. 1 to 4. Assuming that S is a finite set of points 102 in R3 and a satisfies 0≦α≦∞, alpha-hulls and alpha-shapes can be clearly explained as follows:
R3 filled with Styrofoam and the points 102 of S made of a more solid material (e,g., such as rock). Also, there is a spherical eraser 104 with radius α. It is omnipresent in the sense that it carves out Styrofoam at all positions where it does not enclose any of the sprinkled rocks, that is, points 102 of S. The resulting object 106 is referred to as the alpha-hull. To make things more feasible, the surface of the object is straightened by substituting straight edges 108 for the circular ones 110 and triangles for the spherical caps. The obtained object 112 is the alpha-shape of S.
Therefore, an alpha-shape 112 is identical to the convex hull of S when α=∞. For α=0, the alpha-shape 112 reduces to the point set S itself. Generally, alpha-shapes can be concave and disconnected. Alpha-shapes can contain two-dimensional patches of triangles and one-dimensional strings of edges. Its components can even be points. An alpha-shape 112 is a subset of the closure of the Delaunay triangulation of S, and it may have handles and interior voids.
∂X, i(X) and cl(X) denote the boundary, the interior and the closure of a set X, respectively. In addition, Hα(S) and Sα(S) denote an alpha-hull 106 and an alpha-shape 112 of the set S, respectively. Given the above, it can be generally shown that ∂I(Sα(S))≠∂Sα(S). This implies that alpha-shapes 112 are generally non-manifold.
FIG. 1 shows a point set in the plane and an alpha-hull 106 defined on the point set for a particular value of α1. The corresponding alpha-shape 112 for α1 is shown in FIG. 2 with a dangling edge 114. Similarly, FIGS. 3 and 4 illustrate the alpha-hull 106 and alpha-shape 112 of the same input points 102 for α2 where 0<α1<α2. It should be noted herein that the basic idea of alpha-shape presented in the above applies to higher dimensions as well.
Although the theory of alpha-shape has been applied to many situations, there are some critical instances where the application of this construct is not suitable. For such situations, a pocket recognition will be described hereinafter with reference to FIGS. 5 to 7.
First, we will present the definition of a pocket on the surface of a protein in the geometric point of view. At most, most proteins consist of six different types of atoms, i.e., H, C, N, O, P and S, which have the corresponding Van Der Waals radii of 1.2, 1.7, 1.55, 1.52, 1.8 and 1.8 Å, respectively. These atoms with Van Der Waals radii are usually referred to as Van Der Waals atoms. The number of atoms for a protein varies from hundreds to hundreds of thousands.
In most studies conducted to analyze geometric characteristics of a protein with respect to another molecule (usually relatively small) referred to as a ligand, such analysis is typically done using the concept of a spherical probe which encloses the ligand. While a probe is an approximation of the ligand, the probe can best represent the ligand by incorporating its shape, conformation changes, and all possible orientations of the ligand with respect to the protein. Hence, it is considered that the behavior of a probe best represents the geometric behavior of the ligand with respect to a protein. In the case of a water molecule, the corresponding probe is a sphere with the radius of 1.4 Å.
FIG. 5 illustrates has circles 202 (atoms in the plane) of different radii centered at the black dots 204. In this figure, there is a depressed region 206 (referred to as the pocket) on the surface of the given atomic complex and a black circle 208 in the free-space. The black circle 208 is referred to as a beta-ball with radius β. FIG. 5 shows that the beta-ball 208 cannot enter the pocket 206 since the distance between the two larger atoms a1 and ar is not large enough for the beta-ball 208 to pass through.
The method of determining whether or not a beta-ball 208 can freely enter into the pocket 206 or not is discussed below. Ignoring the size differences among the atoms 202 and considering the atom centers 204 only, the best approach for the systematic reasoning of spatial structure may be to use the ordinary Voronoi diagram of the atom centers 204 or the power diagram of atoms. FIG. 6 shows the Voronoi diagram 210 of atom centers 204 and its Delaunay triangulation 212, which is the dual of the Voronoi diagram 210. After enlarging a beta-ball 208 by an appropriate amount to form a beta'-ball 216, the substructure on the protein, which the beta'-ball 208 may pass through, can be detected.
However, the decision of whether the beta-ball 208 can or cannot pass through may not be correct unless the size variation among atoms 202 is properly accounted for. For example, in FIG. 5, the atoms a1 and ar at the entrance are the largest among all atoms 202 in the molecular system. For example, if the beta-ball 208 is enlarged to a beta'-ball 216 by the average of the all atoms 202 in the system, the depressed region 206 can be recognized as being accessible by the beta-ball 208 (shown in FIG. 7). The solid edges 214 in FIG. 7 show the alpha-shape extracted from the Delaunay triangulation 212 in FIG. 6 by removing the Delaunay edges, which the beta-ball 208 can freely pass through. If the beta-ball 208 is enlarged to a beta'-ball by using the largest atom of the system, then a false pocket will not occur in the above-shown example. However, the opposite error can occur in some cases. Assuming that a valid pocket exists where the entrance of the pocket is composed of smaller atoms than other atoms in the molecular system, if the beta-ball is enlarged to a beta-ball by using the largest atom of the system, then the valid pocket cannot be properly recognized in this case. Thus, regardless of the amount of enlargement, there is always the possibility of misjudgment unless the size variation of atoms is fully incorporated. Hence, a combinatorial search is necessary with an alpha-shape to acquire a correct solution and the search is not necessarily local.
Since the ordinary Voronoi diagram of point set (hence the corresponding Delaunay triangulation) does not properly deliver the proximity information among atoms, applications requiring precise proximity information cannot efficiently yield accurate results.
In order to incorporate the size difference among atoms, Edelsbrunner extended the alpha-shape to the weighted alpha-shape using the regular triangulation, which is the topological dual of the power diagram of the atoms (see H. Edelsbrunner, Weighted alpha shapes, Technical Report UIUCDCS-R-92-1760, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Ill. (1992); and H. Edelsbrunner, The union of balls and its dual shape, Discrete & Computational Geometry 13 (1995) 415-440). Since then, the weighted alpha-shapes have been used in restructuring and reasoning of the spatial structure for molecular systems. However, it should be noted that the distance metric in a power diagram is the power distance. In other words, the radius of the spherical eraser is smaller than the minimum tangential distance between the atoms defining an edge or a face. Then, the eraser is considered small enough to pass through between these atoms without a collision and the corresponding edge or face is considered larger than the eraser. As such, it is always necessary in the weighted alpha-shape to check if the minimum Euclidean distance between the atoms defining a bisector in a power diagram really allows for a spherical probe with a predefined size to freely pass through without a collision. Particularly, the power diagram (and therefore the weighted alpha-shape) cannot correctly provide the proximity information among atoms in the Euclidean distance metric, if such atoms do not intersect. Since the power diagram correctly recognizes the intersections between atoms, if the sizes of atoms are properly adjusted, the power diagram of the adjusted atoms may produce correct results. However, the adjustment of atom sizes depends on the particular application. Hence, different applications may require different size adjustments and the computation of power diagram. Besides the computational inefficiency of using power diagram, it is not clear if the size adjustment can be nicely defined for a particular application. Thus, weighted alpha-shapes themselves also have deficiencies in biological applications based on Euclidean distance metric even though they reflect the size variations of atoms at a certain level.